




// 描述
// 对于给定的 int 型的十进制整数 n，统计其在内存中存储时 1 的个数。换句话说，即统计其二进制表示中 1 的个数。
// 输入描述：
// 在一行上输入一个整数 n(0≦n<2^31)
// n(0≦n<2^31)，代表给定的数字。
// 输出描述：
// 在一行上输出一个整数，代表 n 的二进制表示中 1 的个数。


// #include <stdio.h>


// int Count(int n)
// {
//     int retsum=0;
//     for(int i =0;i<32;i++)
//     {
//         if((n&(1<<i))==(1<<i))
//             retsum++;
//     }
//     return retsum;
// }

// int main() {
// int n;
// scanf("%d", &n);
     
// int retnum = Count(n);     
// printf("%d\n", retnum);

//     return 0;
// }



//喝汽水 1瓶汽水1元 2个空瓶可以换一瓶汽水 问给n元可以得到多少瓶汽水
// int main()
// {
// 	int money = 0;
// 	scanf("%d", &money);
// 	int bottle = money;
// 	int empty = money;
	
// 	while (empty>=2)
// 	{
// 		int new = empty / 2;
// 		bottle += new;
// 		empty = empty % 2 + new;
// 	}
// 	printf("%d\n",bottle);
	
// 	return 0;
// }



//将一句话的单词进行倒置，标点不倒置 。比如I like beijing. 经过函数后变为 beijing. like I 
//输入用例长度不超过100 

// void reverse(char* arr, int left, int right)
// {
// 	while (left < right)
// 	{
// 		char tmp = arr[left];
// 		arr[left] = arr[right];
// 		arr[right] = tmp;
// 		left++;
// 		right--;
// 	}
// }

// int main()
// {
// 	char arr[100] = { 0 };
// 	gets(arr); 

// 	int begin = 0;
// 	int end = strlen(arr) - 1;

// 	reverse(arr, begin, end);

// 	begin = 0;
// 	int i = 0;
// 	for (i = 0; i <= end; i++)
// 	{
// 		if (arr[i] == ' ') //使用单引号比较字符
// 		{
// 			reverse(arr, begin, i - 1);
// 			begin = i + 1;
// 		}
// 	}
// 	// 处理最后一个单词
// 	if (i == end + 1)
// 	{
// 		reverse(arr, begin, i - 1);
// 	}

// 	printf("%s", arr);

// 	return 0;
// }


//模拟实现strcpy
// #include <stdio.h>

// // 自定义strcpy函数实现
// char *my_strcpy(char *dest, const char *src) {
//     char *ret = dest;  // 保存目标字符串的起始地址
    
//     // 逐个字符拷贝，直到遇到源字符串的结束符'\0'
//     while ((*dest++ = *src++) != '\0') {
//         ;  // 空循环体
//     }
    
//     return ret;  // 返回目标字符串的起始地址
// }

// int main() {
//     char src[] = "Hello, World!";
//     char dest[20];
    
//     my_strcpy(dest, src);
    
    
//     return 0;
// }



//有序序列合并
// 描述
// 输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。
// 数据范围： 1≤n,m≤1000， 序列中的值满足 0≤val≤30000  
// 输入描述：
// 输入包含三行，
// 第一行包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个数，m表示第三行第二个升序序列中数字的个数。
// 第二行包含n个整数，用空格分隔。
// 第三行包含m个整数，用空格分隔。
// 输出描述：
// 输出为一行，输出长度为n+m的升序序列，即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并。
// #include <stdio.h>

// int ConBine(int n,int* arr1,int m,int* arr2,int* retarr)
// {
//     int i=0;
//     int j=0;
//     int ret_i=0;
//     while(i<n&&j<m)
//     {
//         if((arr1[i]<=arr2[j])&&(i<n&&j<m))
//         {
//             retarr[ret_i]=arr1[i];
//             ret_i++;
//             i++;
//         }
//         if((arr1[i]>arr2[j])&&(i<n&&j<m))
//         {
//             retarr[ret_i]=arr2[j];
//             ret_i++;
//             j++;
//         }
//     }
//     while (i < n) retarr[ret_i++] = arr1[i++];
//     while (j < m) retarr[ret_i++] = arr2[j++];
//     return ret_i;
// }

// int main() {
//     int n=0, m=0;
//     scanf("%d %d",&n,&m);
    
//     int arr1[1000]={0};
//     int arr2[1000] = {0};
//     for(int i=0;i<n;i++)
//     {
//         scanf("%d",&arr1[i]);
//     }
//     for(int i=0;i<m;i++)
//     {
//         scanf("%d",&arr2[i]);
//     }

//     int retarr[2000] = {0};
//     int num = ConBine(n,arr1,m,arr2,retarr);
    
//     for(int i=0;i<num;i++)
//     {
//         printf("%d ",retarr[i]);
//     }
//     return 0;
// }
// //杨式矩阵
// //有一个二维数组.数组的每行从左到右是递增的，每列从上到下是递增的.
// //在这样的数组中查找一个数字是否存在。 时间复杂度小于O(N);


// int find_num(int arr[3][3], int* px, int* py, int k)
// {
// 	int x = 0;
// 	int y = *py - 1;
// 	while (x < *px&&y >= 0)
// 	{
// 		if (k < arr[x][y])
// 		{
// 			y--;
// 		}
// 		else if (k > arr[x][y])
// 		{
// 			x++;
// 		}
// 		else
// 		{
// 			*px = x;
// 			*py = y;
// 			return 1;
// 		}
// 	}
// 	*px = -1;
// 	*py = -1;
// 	return 0;
// }

//   有序序列判断
// 输入一个整数序列，判断是否是有序序列，有序，指序列中的整数从小到大排序或者从大到小排序(相同元素也视为有序)。

// 数据范围： 3≤n≤50  序列中的值都满足 1≤val≤100 
// 输入描述：
// 第一行输入一个整数N(3≤N≤50)。
// 第二行输入N个整数，用空格分隔N个整数。
// 输出描述：
// 输出为一行，如果序列有序输出sorted，否则输出unsorted。

// #include <stdio.h>

// int main() {
//     int n = 0;
//     scanf("%d", &n);
//     int arr[50] = {0};
//     int flag1 = 0;
//     int flag2 = 0;
//     for (int i = 0; i < n; i++) {
//         scanf("%d", &arr[i]);
//         if (i >= 1) 
//         {
//             if (arr[i] < arr[i - 1])
//             {
//                 flag1 = 1;
//             } 
//             else if (arr[i] > arr[i - 1]) 
//             {
//                 flag2 = 1;
//             } else 
//             {
//                 ;
//             }
//         }

//     }
//     if (flag1 + flag2 <= 1)
//         printf("sorted");
//     else
//         printf("unsorted");
//     return 0;
// }

//求两个正整数的最大公约数与最小公倍数之和
// #include <stdio.h>

// int main() {
//     long long n=0;
//     long long m= 0;
//     while(scanf("%lld %lld",&n,&m)==2)
//     {
//         long long tmp1 = n;
//         long long tmp2 = m;
//         long long tmp3  =0;
//         while(tmp3=tmp1%tmp2)
//         {
//             tmp1 = tmp2;
//             tmp2 = tmp3;
//         }//结束后tmp2就是最大公约数
//         // 最小共倍数 为 m*n/最大公约数
//         printf("%lld",(m*n/tmp2+tmp2));

//     }
    
//     return 0;
// }


//260. 只出现一次的数字 III

//给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 
//找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
int* singleNumber(int* nums, int numsSize, int* returnSize) 
{
    int ret =0;
  for(int i=0;i<numsSize;i++)
  {
    ret^=nums[i];
  }
  int m=0;
  while(m<32)
  {
    if(ret&(1U<<m))
    {
       break;
    }
    m++;
  }
    int x=0;
    int y=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]&(1U<<m))
            x^=nums[i];
        else
            y^=nums[i];
    }
    *returnSize=2;
    int* retArray = (int*)malloc(sizeof(int)*2);
    retArray[1]=y;
    retArray[0]=x;

    return retArray;
}
